/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 39891
 * Date: 2025-04-09
 * Time: 18:20
 */
import java.util.Arrays;


public class HashBuck {
    public static class Node{
       public int val;
       public int key;
       public Node next;

       public Node(int key , int val){
           this.key = key;
           this.val = val;
       }
    }

    //hash桶是一个数组，存放每个链表的地址
    Node[] arr = new Node[10];
    public int usedSize ;

    public static final float LOAD_FACTOR = 0.75F;

    public void put(int key , int val){
        //1.通过哈希函数确定位置
        int index = key % arr.length;

        //2.判断是否出现重复的key，然后更新val
        //定义要插入的节点
        Node node = new Node(key,val);
        //已经是要插入数的那个位置了，遍历链表这里是
        Node cur = arr[index];
        //如果出现重复的key，就更新val
        while(cur != null){
            if (cur.key == key){
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        //3.如果没有就使用尾插法插入元素，先写头插
        //这里不用担心next为空，因为不会往后遍历
        /*if(arr[index] == null){
            arr[index] = node;
            先设置头节点 这一步错误会导致node.next指向node，形成环
        }*/
        node.next = arr[index];
        arr[index] = node;
        usedSize++;
        //4.如果负载因子超越了0.75，那么就需要扩容
        if(doLoadFactor() >= LOAD_FACTOR){
            resize();
        }

    }

    private float doLoadFactor(){
        return usedSize*1.0f/ arr.length;    }
    //扩容不能直接复制 ， 要把每一个节点都重新hash到新的数组下标处

    /*for (int i = 0 ; i < arr.length ; i++){
            Node cur = arr[i];
            while(cur != null){
            */
    private void resize(){
        Node[] newArr = Arrays.copyOf(arr, arr.length * 2);
        for (Node node : arr){
            Node cur = node;
            while(cur != null){
                int newIndex = cur.key % newArr.length;
                //然后进行头插 插到新数组下标位置
                Node curN = cur.next;
                cur.next = newArr[newIndex];//如果新数组此处为空 此处cur.next也为空
                newArr[newIndex] = cur;
                cur = curN;             //因为cur还要回原数组便利呢
            }
        }
        arr = newArr; //在放回去
    }
}
